package main

func main() {

	//[1,2,2,null,3,null,3]

	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val:  2,
			Left: nil,
			Right: &TreeNode{
				Val:  3,
				Left: nil,
			},
		},
		Right: &TreeNode{
			Val:  2,
			Left: nil,
			Right: &TreeNode{
				Val:  3,
				Left: nil,
			},
		},
	}
	println(searchBST(root, 2))
}

// 我有点怀疑人生，以前用Java写平衡树和红黑树的插入都现在做个这个，咋都这样了。
func insertIntoBST(root *TreeNode, val int) *TreeNode {

	if root == nil {
		return &TreeNode{Val: val}
	}

	var insertBST func(node *TreeNode)
	insertBST = func(node *TreeNode) {
		if node == nil {
			return
		}

		// 直接挂载，挂完了在把其他的节点下沉...不用挑选合适的位置
		if val < node.Val {
			if node.Left == nil {
				node.Left = &TreeNode{Val: val}
			} else {
				insertBST(node.Left)
			}
		} else {
			if node.Right == nil {
				node.Right = &TreeNode{Val: val}
			} else {
				insertBST(node.Right)
			}
		}
	}

	insertBST(root)

	return root

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
